import random
from collections import deque


def gen_num():
    num = random.randint(1, 1000)
    return num


def gen_num_2():
    num = random.randint(1, 10)
    return num


def gen_list():
    length = random.randint(1, 10)  # 随机生成数组长度
    array = [random.randint(-10, 10) for _ in range(length)]  # 生成随机整数数组
    return array


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def gen_binary_tree():
    num_nodes = random.randint(0, 10)
    # Generate random node values
    node_vals = [random.randint(0, 100) for _ in range(num_nodes)]
    # Create tree from node values
    root = TreeNode(val=node_vals[0])
    q = deque([root])
    i = 1
    while q and i < num_nodes:
        node = q.popleft()
        left_child_val = node_vals[i]
        right_child_val = node_vals[i + 1] if i + 1 < num_nodes else None
        node.left = TreeNode(val=left_child_val)
        q.append(node.left)
        if right_child_val is not None:
            node.right = TreeNode(val=right_child_val)
            q.append(node.right)
        i += 2
    return root


def gen_list():
    nums1 = [random.randint(0, 9) for _ in range(random.randint(0, 100))]
    nums2 = [random.randint(0, 9) for _ in range(random.randint(0, 100))]
    k = random.randint(0, len(nums1) + len(nums2))
    return (nums1, nums2, k)


def gen_permute_list():
    nums = random.sample(range(10), 4)
    return nums


def generate_smallestSubsequence():
    s = ''.join(random.choices('abcdefghijklmnopqrstuvwxyz', k=10))
    letter = random.choice(s)
    count = s.count(letter)
    k = random.randint(1, len(s))
    repetition = random.randint(1, count)
    data = [s, k, letter, repetition]
    return data


def generate_maxProfit():
    prices = [random.randint(1, 100) for _ in range(random.randint(1, 10))]
    return prices


def integerReplacement(self, n: int) -> int:
    count = 0
    while n > 1:
        if n & 1 == 0:  # n 为偶数
            n >>= 1  # 相当于 n = n // 2
        elif n & 3 == 3 and n != 3:  # n 除以 4 余数为 3
            n += 1
        else:
            n -= 1
        count += 1
    return count
def gen_candidates():
    candidates = random.sample(range(2, 41), random.randint(1, 30))
    return candidates
def genz_target():
    target = random.randint(1, 40)
    return target
# 分治
def gen_binaryString():
    binary_string = ''.join(random.choices(['0', '1'], k=32))
    return binary_string
# 贪心
def gen_ratings():
    m = random.randint(1, 2 * 10 ** 4)
    ratings = [random.randint(0, 2 * 10 ** 4) for _ in range(m)]
    return ratings



test_data = {
    'candidates': gen_candidates(),
    'target': genz_target(),
    'bin': gen_binaryString(),
    'ratings': gen_ratings(),
    "integer_replacement": gen_num(),
    "solve_N_queens": gen_num_2(),
    "max_sub_array": gen_list(),
    "splicing_maximum": gen_list(),
    "permute": gen_permute_list(),
    "binaryTreePaths": gen_binary_tree(),
    'smallestSubsequence': generate_smallestSubsequence(),
    'maxProfit': generate_maxProfit(),
    "first_missing_positive": gen_list(),
    'pathWithObstacles': [[0, 0, 0], [0, 1, 0], [0, 0, 0]],
}

if __name__ == '__main__':
    print(test_data["integer_replacement"])
    print(test_data["solve_N_queens"])
    print(test_data["max_sub_array"])
    print(test_data["splicing_maximum"])
    print(test_data["permute"])
    print(test_data["binaryTreePaths"])
